package dynamic;

import java.util.Scanner;

public class 数字三角形 {
    //数字三角形求最小值 PTA上的是求最大值
    //时间复杂度为O(n^2)
    public static void main(String[] args) {
        int n=0;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int a[][] = new int[n][n];
        for(int i=0;i<n;i++){
            for (int j=0;j<=i;j++){
                a[i][j] = sc.nextInt();
            }
        }

        int dp[][] = new int[n][n];
        int pre[][] = new int[n][n];

        search(a,dp,pre);


        int ans = dp[n-1][0];
        int k = 0;
        // 求出最小的ans和对应序列号k
        for(int j=1;j<n;j++){
            if(ans>dp[n-1][j])
                k = j;
            ans = dp[n-1][k];
        }

        System.out.println(dp[n-1][k]);
        //        disPath(k);
    }

    public static void disPath(int k) {

    }

    public static void search(int[][] a,int[][] dp,int[][] pre) {
        //这个求的顺序不能改变
        //考虑到0边界
        dp[0][0] = a[0][0];
        pre[0][0] = -1;
        //考虑到第一列的边界
        for(int i=1;i<a.length;i++){
            dp[i][0] = a[i][0]+dp[i-1][0];
            pre[i][0] = 0;
        }
        //考虑到对角线的边界
        for(int i=1;i<a.length;i++){
            dp[i][i] = a[i][i]+dp[i-1][i-1];
            pre[i][i]= i-1;
        }
        //考虑到有两条路径的情况的节点
        for (int i=1;i< a.length;i++){
            for (int j=1;j<i;j++){
                if(dp[i-1][j-1]<dp[i-1][j]){
                    pre[i][j] = j-1;
                    dp[i][j] = a[i][j]+dp[i-1][j-1];
                }else {
                    pre[i][j] = j;
                    dp[i][j] = a[i][j]+dp[i-1][j];
                }
            }
        }
    }
}
